﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    public class T_0003_IsValidSudoku
    {
        // 有效的数独

        // 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
        //  1.数字 1-9 在每一行只能出现一次。
        //  2.数字 1-9 在每一列只能出现一次。
        //  3.数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

        // 注意：
        //  一个有效的数独（部分已被填充）不一定是可解的。
        //  只需要根据以上规则，验证已经填入的数字是否有效即可。
        //  空白格用 '.' 表示。


        public void Test()
        {
            var board = new char[9][] {
           new char[9] { '5','3','.','.','7','.','.','.','.'},
            new char[9] { '6','.','.','1','9','5','.','.','.'},
            new char[9] { '.','9','8','.','.','.','.','6','.'},
            new char[9] { '8','.','.','.','6','.','.','.','3'},
            new char[9] { '4','.','.','8','.','3','.','.','1'},
           new char[9]  { '7','.','.','.','2','.','.','.','6'},
           new char[9]  { '.','6','.','.','.','.','2','8','.'},
           new char[9]  {'.','.','.','4','1','9','.','.','5' },
           new char[9]  {'.','.','.','.','8','.','.','7','9' }
            };
            var result = IsValidSudoku2(board);
            Console.WriteLine(result);
            Console.Read();
        }

        public bool IsValidSudoku(char[][] board)
        {
            var lines = new int[board.Length, board.Length];
            var columns = new int[board.Length, board.Length];
            var matrixs = new int[board.Length, board.Length];
            for (int i = 0; i < board.Length; i++)
            {
                for (int j = 0; j < board.Length; j++)
                {
                    if (board[i][j] == '.')
                        continue;

                    int value = Convert.ToInt32(board[i][j].ToString()) - 1;
                    int k = i / 3 * 3 + j / 3;

                    if (lines[i, value] == 1 || columns[j, value] == 1 || matrixs[k, value] == 1)
                        return false;
                    else
                        lines[i, value] = columns[j, value] = matrixs[k, value] = 1;
                }
            }
            return true;
        }
        public bool IsValidSudoku2(char[][] board)
        {
            var lines = new int[board.Length];
            var columns = new int[board.Length];
            var matrixs = new int[board.Length];
            int shift;
            for (int i = 0; i < board.Length; i++)
            {
                for (int j = 0; j < board.Length; j++)
                {
                    if (board[i][j] == '.')
                        continue;
                    shift = 1 << (board[i][j] - '0');
                    int k = i / 3 * 3 + j / 3;
                    if ((columns[i] & shift) > 0 || (lines[j] & shift) > 0 || (matrixs[k] & shift) > 0)
                        return false;
                    columns[i] |= shift;
                    lines[j] |= shift;
                    matrixs[k] |= shift;
                }
            }
            return true;
        }
    }
}
